https://leetcode.com/problems/single-number/
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1 :
Input: [2,2,1]
Output: 1
Example 2 :
Input: [4,1,2,1,2]
Output: 4
public class Solution {
public int SingleNumber(int[] nums) {
Dictionary<int, int> dic = new Dictionary<int, int>();
foreach (int num in nums)
{
if (dic.ContainsKey(num))
dic[num] = dic[num] + 1;
else
{
dic.Add(num, 1);
}
}
if (dic.ContainsValue(1))
{
return dic.FirstOrDefault(x => x.Value == 1).Key;
}
else
{
return 0;
}
}
}
Runtime: 96 ms, faster than 99.37% of C# online submissions.
Memory Usage: 27.1 MB, less than 14.29% of C# online submissions.
Time Complexity: O(n)
Space Complextiy: O(n)
這題很簡單
Dictionary 的計算每個數字出現的次數value of dic == 1 的 key 回傳即可。以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉 
我也以為放到 map 去計數最直覺，結果 Java 版的排名只 beats 13% 的人而已
看第一名用 XOR 的原理去做最快
public int singleNumber(int[] nums) {
// XOR http://www.86duino.com/?p=1411&lang=TW
int result = nums[0];
for (int i=1; i<nums.length; i++)
result = result ^ nums[i];
return result;
}
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
相同的數經過 XOR 後只會留下 0
iThome鐵人賽
看影片追技術